/**
 * @Author: Liu, Yunfeng
 * @DateTime: 2021/3/4 1:00
 * @Description: 需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
 */
public class climbStairs {
    public static int climbStairs(int n) {
        int[] a = new int[3];
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        a[0] = 1;
        a[1] = 2;
        a[2] = 0;
        for (int i = 3; i <= n; i++) {
            a[2] = a[1] + a[0];
            a[0] = a[1];
            a[1] = a[2];
        }
        return a[2];
    }

    public static void main(String[] args) {
        System.out.println(climbStairs(4));
    }
}
/*
* f(n) = f(n-1)+f(n-2);
* */